package com.sl.map;

/**
 * author： suliang
 * 2022/12/15 11:06
 * describe : Hashmap 数据结构
 */
public class SLHashMap<K, V> implements SLMap<K, V> {

    static final float DEFAULT_LOAD_FACTOR = 0.75f;
    static final int MAXIMUM_CAPACITY = 1 << 30;
    Node[] table = null;
    static int threshold = 0;
    private int size;
    public SLHashMap() {
//        性能最优秀
        threshold = 1 << 4;
        table = new Node[threshold];
    }
    public SLHashMap(int tablesize) {
//        性能最优秀
        threshold = 1 << 4;
        table = new Node[tablesize];
    }

    int tableSizeFor(int cap) {
        int n = cap - 1;
        n |= n >>> 1;
        n |= n >>> 2;
        n |= n >>> 4;
        n |= n >>> 8;
        n |= n >>> 16;
        return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
    }
    //    扩容
    private void resize() {
        threshold = threshold << 1;  //threshold<<1
        Node<K, V>[] newtable = new Node[threshold];
        for(int i = 0;i<table.length;i++){
//            取出头  oldNode  david
            Node<K, V> oldNode = table[i];
//            oldNode  river
            while (oldNode != null) {
//              oldNode=  river   oldNext=zee
                Node oldNext = oldNode.next;
//新的索引
                int index = hash(oldNode.getKey()) & (newtable.length - 1);
//                oldNode  david  oldNode.next=null  newtable[index]=david
                oldNode.next=newtable[index];
//david    oldNode river
                newtable[index] = oldNode;
//                链表遍历
                oldNode=oldNext;
            }
        }

    }
    @Override
    public V put(K key, V value) {
        if (table == null) {
            table = new Node[threshold];
        }
        if (size > DEFAULT_LOAD_FACTOR * threshold) {
            resize();
        }
        int index = hash(key) & threshold - 1;
        Node<K, V> node=table[index];
        if (node == null) {
            node = new Node<>(key, value, null);
            size++;
        }else {
//            找到david
            Node<K, V> newNode = node;
//
            while (newNode != null) {
                if (newNode.getKey().equals(key)) {
                    return newNode.setValue(value);
                }else {
                    if (newNode.next == null) {
//                        前面的node  river     node david
                        node  = new Node<>(key, value, node);
                        size++;
                    }
                }
                newNode = newNode.next;
            }

        }
//99号技师  river
        table[index] = node;
        return null;
    }
    static final int hash(Object key) {
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }

    @Override
    public V get(K key) {
        int index = hash(key.hashCode()) & (threshold - 1);
        Node node = table[index];
        return (V) getNode(node, key).getValue();
    }
    public Node<K, V> getNode(Node<K, V> node,K k){
        while(node!=null){
            if(node.getKey().equals(k)||node.getKey()==k){
                return node;
            }
            node=node.next;
        }
        return node;
    }

    @Override
    public int size() {
        return 0;
    }

    //键   值
    class Node<K, V> implements SLHashMap.Entry<K, V> {
        private K key;
        private V value;
        private Node<K, V> next;

        public Node(K key, V value, Node<K, V> next) {
            super();
            this.key = key;
            this.value = value;
            this.next = next;
        }

        @Override
        public K getKey() {
            return key;
        }

        @Override
        public V getValue() {
            return value;
        }

        @Override
        public V setValue(V value) {
            this.value = value;
            return null;
        }
    }
    public void print() {
        for (int i = 0; i < table.length; i++) {
            Node<K, V> node = table[i];
            System.out.print("下标位置[" + i + "]");
            while (node != null) {
                System.out.print("[ key:" + node.getKey() + ",value:" + node.getValue() + "]");
                node = node.next;

            }
            System.out.println();
        }
    }
}
